Packet switching is the core technology of the Internet. The Internet consists of end-hosts, links, and routers. A router consists of several processing stages. At the very least, a router has two main processing stages: address lookup and switching. This patent focuses on the switching stage of the Routers/Switches.

Network operators would like to build their networks using routers that give performance guarantees. They want routers that provide throughput, bandwidth and delay guarantees. For example, large corporations might want to guarantee a fixed bandwidth between their company sites. Similarly, if a network operator can guarantee a maximum delay through their network, they can also sell services to customers who run real-time applications such as video and voice.
FIG. 1 is an illustration of an architecture of a buffered crossbar with three ports. This is a buffered Crossbar that includes an internal FIFO in cross points. A buffered Crossbar running at a speedup of two can also behave identically to an OQ switch. The scheduler for a buffered crossbar allows inputs and outputs to schedule independently and in parallel making it much simpler and, therefore, more practical than for a traditional unbuffered crossbar. Simplifying the scheduler comes at the expense of a more complicated crossbar; it now has to hold and maintain N2 packet buffers. Generally, in a buffered crossbar, the buffer size of each FIFO buffer should be at least twice the amount of traffic that can arrive at a crossbar port over the roundtrip time delay of a control signal exchanged between the Line Card and the Crossbar. The roundtrip time delay (RTT) is in the order of 600 to 800 ns. As a result, for 10 Gbps line rate, the minimum size of each FIFO buffer becomes 2 Kbytes.
Minimum Internal Buffer Size: 2*N*N Kbytes.
NBuffer Size (Mbytes)Number Of FIFOs160.5 256322.01024648.04096 (non manufacturable)
Current buffered crossbar switch architectures require the use of N*N buffers for an N port switch. This memory requirement severely limits the number of ports that a single chip can handle. This limitation is due to the fact that on-chip memory is very expensive in terms of cost and space. With current processes and switch architectures, the largest realizable switch fabric which could support packets with Variable size up to 2 KBytes can be at most 32×32 with very big internal memory. Current buffered crossbar switch architectures do not Support Jumbo packets with Variable Packet size up to 64 Kbytes with switch size more than 8×8.
Thus, there exists a need in the art for a buffered crossbar that requires less space for buffers, yet that delivers desired performance. As will be seen, the invention provides this in a novel and elegant manner.